import java.awt.color.ICC_ColorSpace;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution1 {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = "" + nums[i];
        }
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuffer ret = new StringBuffer();
        for (int i = 0; i < n; i++) {
            ret.append(strs[i]);
        }
        if (ret.charAt(0) == '0') return "0";
        return ret.toString();
    }
}

class Solution2 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int count = 0;
        int left = 0;
        for (int i = 0; i < n - 1; i++) {
            int right = nums[i+1] - nums[i];
            if(right == 0) continue;
            if(left * right <= 0) count++;
            left = right;
        }

        return count + 1;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        for(int i = 1; i < n; i++) {
            if(nums[i] > list.get(list.size()-1)) {
                list.add(nums[i]);
            }else {
                int left = 0, right = list.size()-1;
                while(left <= right) {
                    int mid = left + (right - left) / 2;
                    if(nums[i] > list.get(mid)) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                list.set(left, nums[i]);
            }
        }
        return list.size();
    }
}


public class Main {
}
